#define _CRT_SECURE_NO_WARNINGS


//struct ListNode* removeElements(struct ListNode* head, int val) {
//    struct ListNode* cur = head;
//    struct ListNode* tail = NULL, * newhead = NULL;
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    while (cur)
//    {
//        if (cur->val != val)
//        {
//            if (tail == NULL)
//            {
//                tail = newhead = cur;
//            }
//            else
//            {
//                tail->next = cur;
//                tail = tail->next;
//            }
//            cur = cur->next;
//        }
//        else
//        {
//            struct ListNode* next = cur->next;
//            free(cur);
//            cur = next;
//        }
//    }
//    if (tail)
//    {
//        tail->next = NULL;
//    }
//    return newhead;
//}


//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* cur = head;
//    struct ListNode* rhead = NULL;
//    while (cur)
//    {
//        struct ListNode* tmp = cur->next;
//        cur->next = rhead;
//        rhead = cur;
//        cur = tmp;
//    }
//    return rhead;
//}


//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* cur = head;
//    int count = 0;
//    while (cur)
//    {
//        count++;
//        cur = cur->next;
//    }
//    for (int i = 1; i < count / 2 + 1; i++)
//    {
//        head = head->next;
//    }
//    return head;
//}



//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//    // write code here
//    struct ListNode* cur = pListHead;
//    int count = 0;
//    while (cur)
//    {
//        count++;
//        cur = cur->next;
//    }
//    if (k > count)
//    {
//        return NULL;
//    }
//    for (int i = 1; i <= count - k; i++)
//    {
//        pListHead = pListHead->next;
//    }
//    return pListHead;
//}


//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    if (list1 == NULL)
//    {
//        return list2;
//    }
//    if (list2 == NULL)
//    {
//        return list1;
//    }
//    struct ListNode* newhead = NULL, * cur = NULL;
//    while (list1 && list2)
//    {
//        if (list1->val < list2->val)
//        {
//            if (newhead == NULL)
//            {
//                newhead = cur = list1;
//            }
//            else
//            {
//                cur->next = list1;
//                cur = cur->next;
//            }
//            list1 = list1->next;
//        }
//        else
//        {
//            if (newhead == NULL)
//            {
//                newhead = cur = list2;
//            }
//            else
//            {
//                cur->next = list2;
//                cur = cur->next;
//            }
//            list2 = list2->next;
//        }
//    }
//    if (list1)
//    {
//        cur->next = list1;
//    }
//    if (list2)
//    {
//        cur->next = list2;
//    }
//    return newhead;
//}




//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    struct ListNode* newhead, * cur;
//    newhead = cur = (struct ListNode*)malloc(sizeof(struct ListNode));
//    newhead->next = NULL;
//    while (list1 && list2)
//    {
//        if (list1->val < list2->val)
//        {
//            cur->next = list1;
//            cur = cur->next;
//            list1 = list1->next;
//        }
//        else
//        {
//            cur->next = list2;
//            cur = cur->next;
//            list2 = list2->next;
//        }
//    }
//    if (list1)
//    {
//        cur->next = list1;
//    }
//    if (list2)
//    {
//        cur->next = list2;
//    }
//    struct ListNode* tmp = newhead->next;
//    free(newhead);
//    return tmp;
//}